/*
    Copyright 2006 Andrew Wilkinson <andrew@indiegigs.co.uk>

    This file is part of libgp2x.

    libgp2x is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    libgp2x is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with libgp2x; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/

#include <ctype.h>

#define NO_INTERNAL
#include "gp2x_internal.h"

int qsort_reorder(void* base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));

void qsort(void* base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
    int pivot = qsort_reorder(base, nmemb, size, compar);
    if(pivot == -1) {
        return;
    } else if(pivot == 0) {
        qsort(base+size, nmemb-1, size, compar);
    } else if(pivot == nmemb-1) {
        qsort(base, nmemb-1, size, compar);
    } else {
        qsort(base, pivot, size, compar);
        qsort(base+size*(pivot+1), nmemb-pivot, size, compar);
    }
}

void qsort_swap(void* p1, void* p2, size_t size) {
    void* tmp = malloc(size);
    memcpy(tmp, p1, size);
    memcpy(p1, p2, size);
    memcpy(p2, tmp, size);
}

int qsort_reorder(void* base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
    if(nmemb <= 1) {
        return -1;
    } else if(nmemb == 2) {
        if(compar(base, base+size) < 0) {
            qsort_swap(base, base+size, size);
        }
        return -1;
    } else {
        int i;
        int storeIndex = 0;
        void* pivotptr = base + size*(nmemb-1);
        qsort_swap(base+size*(nmemb/2), base+size*(nmemb-1), size);
        for(i=0; i<size-1; i++) {
            if(compar(base+size*i, pivotptr) <= 0) {
                qsort_swap(base+size*storeIndex, base+size*i, size);
                storeIndex += 1;
            }
        }
        return storeIndex;
    }
}
